class Solution {
    //从第一个元素开始，定义两个指针，前面一个用于查找偶数，后面一个用于查找奇数
    //目标是确保奇数全被交换到数组的前半部分,时间复杂度O(n)
    //考虑将循环条件单独写入一个函数，并使用函数指针的形式调用，提高代码的可重用性
public:
    vector<int> exchange(vector<int>& nums) {
        int first = 0;
        int last = nums.size() - 1;  //注意下标越界问题

        bool (*func)(int) = isEven;

        while(first < last){

            while(first < last && !func(nums[first]))  ++first;  //找到位于数组前半部分的偶数

            while(first < last && func(nums[last]))  --last;  //找到位于数组后半部分的奇数

            if(first < last){
                //交换奇偶数
                int temp = nums[first];
                nums[first] = nums[last];
                nums[last] = temp;
            }
        }

        return nums;
    }

    //判断是否是偶数,若是偶数返回true,反之则为false
    static bool isEven(int n){
        return (n & 1) == 0;
    }
};